The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to a structure and method for implementing wide multiplexers in an FPGA using a horizontal chain structure.
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that may be programmed by a user to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
One such FPGA, the Xilinx Virtex(copyright) FPGA, is described in detail in pages 3-75 through 3-96 of the Xilinx 2000 Data Book entitled xe2x80x9cThe Programmable Logic Data Book 2000xe2x80x9d (hereinafter referred to as xe2x80x9cthe Xilinx Data Bookxe2x80x9d), published April, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference. (Xilinx, Inc., owner of the copyright, has no objection to copying these and other pages referenced herein but otherwise reserves all copyright rights whatsoever.)
The Virtex CLB is composed of two similar elements called xe2x80x9cslicesxe2x80x9d, as described by Young et al. in U.S. Pat. No. 5,920,202 and shown in FIGS. 4A and 4B therein. (U.S. Pat. No. 5,920,202 is hereby incorporated herein by reference.) These figures are reproduced in FIGS. 1A and 1B of the present specification. Young et al. describe the figures in detail, therefore, the description is not repeated here.
FIG. 2 is a simplified drawing of the Virtex CLB of FIGS. 1A and 1B, showing how the F5 and F6 multiplexers of the two slices can be interconnected to implement wide functions. The two slices are designated SA and SB. Included in FIG. 2 are the four 4-input function generators F, G, H, J. The outputs of function generators F and G (Fxe2x80x2 and Gxe2x80x2, respectively) are combined with a fifth independent input BFF in multiplexer F5B to produce output F5Bxe2x80x2, which can be any function of five inputs, or some functions of up to nine inputs. (In the present specification, the same reference characters are used to refer to terminals, signal lines, and their corresponding signals.) The outputs of function generators H and J (Hxe2x80x2 and Jxe2x80x2, respectively) are combined with a fifth independent input BHH in multiplexer F5A to produce output F5Axe2x80x2, which can be any function of five inputs, or some functions of up to nine inputs.
The outputs F5Axe2x80x2 and F5Bxe2x80x2 of multiplexers F5A and F5B are combined with a sixth independent input BGG in multiplexer F6B, and with a different sixth independent input BJJ in multiplexer F6A. The two multiplexers F6A and F6B therefore produce two outputs F6Axe2x80x2 and F6Bxe2x80x2, respectively. One of outputs F6Axe2x80x2 and F6Bxe2x80x2 can be any function of six inputs; the other output can be any function of six inputs provided that five inputs are shared between the two 6-input functions. Some functions of up to nineteen inputs can also be generated in a single CLE.
As described above, the four 4-input function generators F, G, H, J shown in FIGS. 1A, 1B, and 2 can each be used to implement any function of up to four inputs. Therefore, each function generator can implement one 2-to-1 multiplexer. The F and G function generators and the F5B multiplexer can together implement a 4-to-1 multiplexer. Similarly, the outputs of the H and J function generators can be combined in the F5A multiplexer to implement another 4-to-1 multiplexer. The four function generators, the two F5 multiplexers, and one of the F6 multiplexers can together implement an 8-to-1 multiplexer.
However, this multiplexer implementation is limiting in that the entire multiplexer is implemented as a compact block instead of as a distributed structure. In some applications, it is desirable to implement a multiplexer in such a fashion that the floorplan matches the layout of other circuits in the application. Thus, for applications such as datapaths and ALUs, for example, it is desirable to implement a wide multiplexer as a structure distributed along a horizontal chain of slices. Further, the fact that carry chains are often implemented in a vertical fashion means that a horizontal multiplexer would be efficient in emulating the internal busses that are often used in datapaths, ALUs, and other ordered circuit structures. Therefore, it is desirable to provide structures and methods for implementing multiplexers along a horizontal chain of logic elements in an FPGA.
The invention provides methods and structures for implementing wide multiplexers in programmable logic devices (PLDs) such as Field Programmable Gate Arrays (FPGAs). According to a first embodiment, a configurable logic structure includes a function generator, a carry multiplexer, and an OR gate. The function generator is configured to implement a multiplexing function (under control of a first select signal) and an AND function (ANDing the output of the multiplexer with a second select signal). By ANDing the output of the multiplexer with the second select signal, a second level of multiplexing can be added by selectively setting the values of the second select signal in different ones of the logic structures. The carry multiplexer is configured to perform an AND function between an output of the function generator and a third select signal. Again, various values of the third select signal can be used on different ones of the logic structures. Thus, with three select signals available, an 8-to-1 multiplexer can be implemented by combining the outputs of four different logic structures that use different values of the select signals. This combination of outputs is performed by forming an OR chain, with the OR input of each stage being provided by the associated carry multiplexer. The OR input of the first stage is a logic low value; the OR output of the final stage is the output of the wide multiplexer function.
As will be clear to those of ordinary skill in the art of PLD design, the 8-to-1 multiplexer described herein is purely exemplary, and wide multiplexers of virtually any size can be formed using the structures and methods of the invention. The described multiplexer is merely selected as being particularly suited to implementation in the Virtex-II FPGA architecture from Xilinx, Inc., where a distributed 8-to-1 multiplexer can be implemented in four function generators.
The distributed multiplexing function of the invention has advantages for certain applications having structured layouts, such as ALUs and other datapath functions. For example, the distributed structure of the invention allows the emulation of internal busses used within the application. Also, having a multiplexer structure distributed along with the related logic can reduce path delays. Further, the number of CLBs required to implement many user designs is reduced, because (in one embodiment) only a portion of the logic within the configurable logic structure is used. The unused resources are still available to implement other user functions.
Another advantage of the described embodiment is that each circuit element used to implement the multiplexing function has another use for which it was primarily designed. The carry multiplexer is primarily used to implement carry chains. The OR gate is primarily used to perform a Sum-Of-Products function. Therefore, in the preferred embodiment, no extra circuitry need be added to the CLB to enable the invention.
A second aspect of the invention comprises methods for implementing wide multiplexing circuits in PLDs. According to one embodiment, a wide multiplexing circuit comprising a plurality of multiplexing structures is implemented by: configuring a function generator of each multiplexing structure to implement a first multiplexer; implementing a carry multiplexer of each multiplexing structure as an AND gate performing an AND function between the output of the first multiplexer and an external select signal; and configuring an OR gate of each multiplexing structure to form an OR chain to combine the outputs of the various carry multiplexers. The output of the last OR gate in the chain is the output of the wide multiplexing circuit.